package lru

import "container/list"

type Cache struct {
	maxBytes  int64                         // 允许使用最大内存
	nBytes    int64                         // 当前已使用内存
	ll        *list.List                    // 双向链表
	cache     map[string]*list.Element      // 键是字符串 值是指向双向链表中对应节点的指针
	OnEvicted func(key string, value Value) // 某条记录被移除时的回调函数 可以为nil
}

type entry struct { // 键值对entry 双向链表节点的数据类型
	key   string
	value Value
}

type Value interface { // 为了通用性 我们允许值是实现了Value接口的任意类型 该接口只包含了一个方法 Len() int 用于返回值所占用的内存大小
	Len() int
}

// 创建一个新的Cache实例
func New(maxBytes int64, onEvicted func(string, Value)) *Cache {
	return &Cache{
		maxBytes:  maxBytes,
		OnEvicted: onEvicted,
		ll:        list.New(),
		cache:     make(map[string]*list.Element),
	}
}

// Get 查找
func (c *Cache) Get(Key string) (value Value, ok bool) {
	if ele, ok := c.cache[Key]; ok {
		c.ll.MoveToFront(ele) // 将该节点移动到队尾 即最近使用 双向链表是一个队列，约定front是队首
		kv := ele.Value.(*entry)
		return kv.value, true
	}
	return
}

// RemoveOldest 移除最近最少使用的元素
func (c *Cache) RemoveOldest() {
	ele := c.ll.Back() // 取到队首元素
	if ele != nil {
		c.ll.Remove(ele)
		kv := ele.Value.(*entry)
		delete(c.cache, kv.key)
		c.nBytes -= int64(len(kv.key)) + int64(kv.value.Len()) // 将当前已使用内存更新为删去队首元素后的内存大小
		if c.OnEvicted != nil {
			// 回调
			c.OnEvicted(kv.key, kv.value)
		}
	}
}

// Add 添加/修改
func (c *Cache) Add(key string, value Value) {
	if ele, ok := c.cache[key]; ok {
		c.ll.MoveToFront(ele) // 如果键存在，更新对应节点的值，并将其放到队尾
		kv := ele.Value.(*entry)
		c.nBytes += int64(value.Len()) - int64(kv.value.Len()) // 将当前使用内存更新为修改之后的内存大小
		kv.value = value
	} else {
		ele := c.ll.PushFront(&entry{key, value}) // 队尾添加新节点，在字典中添加key和节点的映射
		c.cache[key] = ele
		c.nBytes += int64(len(key)) + int64(value.Len())
	}
	for c.maxBytes != 0 && c.maxBytes < c.nBytes {
		c.RemoveOldest()
	}
}

func (c *Cache) Len() int {
	return c.ll.Len()
}
